package com.wj.algorithm.lintcode;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class P46 {
    /*
     * @param nums: a list of integers
     * @return: find a  majority number
     */
    public int majorityNumber(List<Integer> nums) {
        // write your code here
        if(nums == null || nums.size() < 1) {
            return -1;
        }
        
        int v = 0, count = 0, len = nums.size();
        Collections.sort(nums);
        v = nums.get(0);
        count = 1;
        for(int i = 1; i < len; i ++) {
            if(v == nums.get(i)) {
                count ++;
                if(count > len / 2) {
                    return v;
                }
            } else {
                v = nums.get(i);
                count = 1;
            }
        }
        
        return v;
    }
    public static void main(String[] args) {
        System.out.println(new P46().majorityNumber(Arrays.asList(new Integer[]{0})));
    }
}
